This application claims the priority of Korean Patent Application No. 2002-10981, filed Feb. 28, 2002, in the Korean Intellectual Property Office, the disclosure of which is incorporated herein in its entirety by reference.
1. Field of the Invention
The present invention relates to an improved Huffman decoding method and apparatus, and more particularly, to a Huffman decoding method and apparatus that performs Huffman decoding by constructing an efficient one-dimensional look-up table generated from a binary tree, and by using a numerical method for improving processing efficiency.
2. Description of the Related Art
Because of the unique characteristics of the Huffman code, the related art Huffman decoding method using a binary tree is considered a very efficient method based on maximum search time, average search time, and search time deviation. However, according to the search method based on the related art binary tree, to generate a data structure for searching, a complicated process is required for constructing a binary tree based on a linked list. Also, comparison and branch statements for transition between nodes in a binary tree search slow the processing flow of the operations of a related art processor, thereby decreasing the processing speed of a Huffman decoder.
The structure and operation of the prior art Huffman decoding apparatus and method will now be explained referring to accompanying drawings.
FIG. 1 is a schematic block diagram of the related art Huffman decoding apparatus. The apparatus comprises an input buffer 110 that receives an encoded bit stream, a search engine 120, a Huffman look-up table 130, and an output buffer 140 that outputs decoded Huffman data.
FIG. 2 is a flowchart of the prior art Huffman decoding method of a Huffman decoder based on a related art conditional branch statement. This method is performed in the apparatus shown in FIG. 1, and is described in greater detail below.
FIG. 3 is a diagram showing a binary Huffman tree structure according to the related art method. Nodes 310, 322, 330, 332, 342, 344, and 356 are internal nodes that branch to next nodes. Nodes 320, 340, 346, 350, 352, 354, 360, and 362 are terminal nodes that have return values to be actually sent back.
Table 1 is a codebook of the binary Huffman tree shown in FIG. 3.
FIGS. 4a and 4b are diagrams showing the memory structure of a Huffman table according to the related art binary tree Huffman decoding method. As shown in FIGS. 4a and 4b, the prior art Huffman table uses 3 memory spaces. As shown in FIG. 4a, for an internal node, a null value is stored in the middle memory space among the allocated 3 memory spaces, the address of a left-hand node of the children nodes is stored in the left-hand memory space, and the address of a right-hand node of the children nodes is stored in the right-hand memory space. Also as shown in FIG. 4b, for a terminal node, an internal value of the node, that is, a return value to be sent back, is stored in the middle memory space of the allocated 3 memory spaces, and null values are stored in the left-hand and right-hand memory spaces.
Referring to FIGS. 3 through 5, and based on the flowchart shown in FIG. 2, the decoding method of a Huffman decoder using the Huffman table of the prior art binary tree structure will be explained below.
In step S210, a first step of decoding, based on the codeword of an encoded bit stream input to the Huffman decoder, an entry corresponding to a root node of the Huffman tree shown in FIG. 3 (i.e., the internal node 310) is accessed. In step S220, a comparison and branch statement, it is determined whether the node corresponding to the entry accessed in the step S210 is an internal node or a terminal node.
In step S230, if it is determined in step S220 that the node corresponding to the accessed entry is a terminal node, a value stored in the middle memory space among the 3 memory spaces allocated to the terminal node is output as a decoded codeword value to be sent back. Alternatively, in step S240, if it is determined in step S220 that the node corresponding to the accessed entry is an internal node, it is determined whether the value of 1 bit input from the bit stream is xe2x80x980xe2x80x99 or xe2x80x981xe2x80x99. If the value is xe2x80x980xe2x80x99, step S250 is performed. If the value is xe2x80x981xe2x80x99, step S260 is performed.
In step S250, an entry corresponding to an address stored in the left-hand memory space among the 3 memory spaces allocated to the current node is accessed, and step S220 is then performed. Alternatively, in step S260, an entry corresponding to an address stored in the right-hand memory space among the 3 memory spaces allocated to the current node is accessed, and step S220 is then performed.
Referring to FIGS. 2 and 5, a process for decoding an input bit stream xe2x80x981110100 . . . xe2x80x99, which is encoded according to the prior art Huffman decoding method described above, will now be explained.
In step S210, an entry corresponding to the root address of the Huffman binary tree (the entry which corresponds to address xe2x80x981xe2x80x99 of the Huffman table shown in FIG. 5) is accessed.
In step S220, it is determined whether the node of the accessed entry is an internal node or a terminal node. Referring to FIG. 5, the value stored in the middle memory space of the 3 memory spaces of the node corresponding to address xe2x80x981xe2x80x99 is xe2x80x98NULLxe2x80x99, xe2x80x984xe2x80x99 is stored in the left-hand memory space and xe2x80x987xe2x80x99 is stored in the right-hand memory space. Accordingly, in step S220 it is determined that the node corresponding to the address xe2x80x981xe2x80x99 is an internal node shown in FIG. 4a, and accordingly, step S240 is performed.
In step S240, the first bit xe2x80x981xe2x80x99 of the first encoded codeword of the input bit stream xe2x80x981110100xe2x80x99 is input. Because the input bit (new digit( )) is xe2x80x981xe2x80x99, step S260 is performed.
In step S260, an entry corresponding to address xe2x80x987xe2x80x99 stored in the right-hand address xe2x80x982xe2x80x99 of the current address xe2x80x981xe2x80x99, that is, in the right-hand memory space of the current node, is accessed, and step S220 is performed.
In the step 220, it is determined whether the node corresponding to the address xe2x80x987xe2x80x99 of the Huffman table is an internal node or a terminal node. Referring to FIG. 5, the value stored in the middle memory space of the 3 memory spaces of the node corresponding to address xe2x80x987xe2x80x99 is xe2x80x98NULLxe2x80x99, xe2x80x9810xe2x80x99 is stored in the left-hand memory space and xe2x80x9813xe2x80x99 is stored in the right-hand memory space. Accordingly, in step S220 it is determined that the node corresponding to the address xe2x80x987xe2x80x99 is an internal node shown in FIG. 4a, and step S240 is performed.
In step S240, the second bit xe2x80x981xe2x80x99 of the first encoded codeword of the input bit stream xe2x80x981110100xe2x80x99 is input. Because the input bit (new digit( )) is xe2x80x981xe2x80x99, step S260 is performed.
In step S260, an entry corresponding to address xe2x80x9813xe2x80x99 stored in the right-hand address xe2x80x988xe2x80x99 of the current address xe2x80x987xe2x80x99, that is, in the right-hand memory space of the current node, is accessed, and step S220 is performed.
In step S220, it is determined whether the node corresponding to the address xe2x80x9813xe2x80x99 of the Huffman table is an internal node or a terminal node. Referring to FIG. 5, the value stored in the middle memory space of the 3 memory spaces of the node corresponding to address xe2x80x9813xe2x80x99 is xe2x80x98NULLxe2x80x99, xe2x80x9822xe2x80x99 is stored in the left-hand memory space and xe2x80x9825xe2x80x99 is stored in the right-hand memory space. Accordingly, in step S220 it is determined that the node corresponding to the address xe2x80x9813xe2x80x99 is an internal node shown in FIG. 4a, and step S240 is performed.
In step S240, the third bit xe2x80x981xe2x80x99 of the first encoded codeword of the input bit stream xe2x80x981110100xe2x80x99 is input. Because the input bit (new digit( )) is xe2x80x981xe2x80x99, step S260 is performed.
In step S260, an entry corresponding to address xe2x80x9825xe2x80x99 stored in the right-hand address xe2x80x9814xe2x80x99 of the current address xe2x80x9813xe2x80x99, that is, in the right-hand memory space of the current node, is accessed, and step S220 is performed.
In step S220, it is determined whether the node corresponding to the address xe2x80x9825xe2x80x99 of the Huffman table is an internal node or a terminal node. Referring to FIG. 5, the value stored in the middle memory space of the 3 memory spaces of the node corresponding to address xe2x80x9825xe2x80x99 is xe2x80x984xe2x80x99, xe2x80x98NULLxe2x80x99 is stored in the left-hand memory space and xe2x80x98NULLxe2x80x99 is stored in the right-hand memory space. Accordingly, in step S220 it is determined that the node corresponding to the address xe2x80x9825xe2x80x99 is a terminal node shown in FIG. 4a, and step S230 is performed.
In the step 230, the value xe2x80x984xe2x80x99 stored in the middle memory space among the 3 memory spaces allocated to the node corresponding to the address xe2x80x9825xe2x80x99 is output as a decoded codeword value.
Accordingly, the decoded codeword xe2x80x984xe2x80x99 corresponding to the first codeword xe2x80x98111xe2x80x99 of the input bit stream xe2x80x981110100xe2x80x99 is obtained, and decoding of the second codeword of the bit stream xe2x80x981110100xe2x80x99 is performed.
In the same manner as in the process for obtaining the decoded codeword value xe2x80x984xe2x80x99, in step S210 as the first step of the decoding, an entry corresponding to address xe2x80x981xe2x80x99 of the Huffman table, that is, the root address of the Huffman binary tree, is accessed and then step S220 is performed.
In step S220, it is determined whether the accessed node corresponding to the address xe2x80x981xe2x80x99 of the Huffman table is an internal node or a terminal node. The value stored in the middle memory space of the 3 memory spaces of the node corresponding to address xe2x80x981xe2x80x99 is xe2x80x98NULLxe2x80x99, xe2x80x984xe2x80x99 is stored in the left-hand memory space and xe2x80x987xe2x80x99 is stored in the right-hand memory space. Accordingly, in the step 220 it is determined that the node corresponding to the address xe2x80x981xe2x80x99 is an internal node shown in FIG. 4a, and step S240 is performed.
In step S240, the first bit xe2x80x980xe2x80x99 of the second codeword of the input bit stream xe2x80x981110100xe2x80x99 is input. Because the input bit (new digit( )) is xe2x80x980xe2x80x99, step S250 is performed.
In step S250, an entry corresponding to the address xe2x80x984xe2x80x99 stored in the left-hand address xe2x80x980xe2x80x99 of the current address xe2x80x981xe2x80x99, that is, the left-hand memory space of the current node, is accessed and step S220 is performed.
In step S220, it is determined whether the node corresponding to the address xe2x80x984xe2x80x99 of the Huffman table is an internal node or a terminal node. Referring to FIG. 5, the value stored in the middle memory space of the 3 memory spaces of the node corresponding to address xe2x80x984xe2x80x99 is xe2x80x9860xe2x80x99, xe2x80x98NULLxe2x80x99 is stored in the left-hand memory space and xe2x80x98NULLxe2x80x99 is stored in the right-hand memory space. Accordingly, in step S220 it is determined that the node corresponding to the address xe2x80x984xe2x80x99 is a terminal node shown in FIG. 4a, and step S230 is performed.
In step S230, the value xe2x80x9860xe2x80x99 stored in the middle memory space among the 3 memory spaces allocated to the node corresponding to the address xe2x80x984xe2x80x99 is output as a decoded codeword value corresponding to the second codeword xe2x80x980xe2x80x99 of the bit stream xe2x80x981110100xe2x80x99.
In this manner, the decoded codeword value xe2x80x9859xe2x80x99 corresponding to the third codeword xe2x80x98100xe2x80x99 of the encoded bit stream xe2x80x981110100xe2x80x99 input to the Huffman decoder is output. By doing so, decoded codeword values xe2x80x984, 60, 59, . . . xe2x80x99 corresponding to the bit stream xe2x80x981110100 . . . xe2x80x99 are obtained.
The related art has various problems and disadvantages. For example, but not by way of limitation, in the related art Huffman decoding method based on a binary tree, a complicated process for generating a binary tree based on a linked list should be performed to generate a data structure needed for searching. In particular, comparison and branch statements for transition between nodes in a binary tree search reduces the processing flow of the operations of a processor such that the efficiency of the operational speed decreases. Also, since each node uses 3 memory spaces in the look-up table according to the related art Huffman decoding method, memory spaces are excessively consumed.
The present invention provides an improved Huffman decoding method by which the related art xe2x80x98comparison and branchxe2x80x99 command that decreases processing efficiency in the prior Huffman decoding process can be omitted so that the operational speed of a Huffman decoder can increase, and required memory resources can decrease.
The present invention also provides an improved Huffman decoding system which performs the improved Huffman decoding method by which the related art xe2x80x98comparison and branchxe2x80x99 command that decreases processing efficiency in the prior Huffman decoding process can be omitted, so that the operational speed of a Huffman decoder can increase, and required memory resources can decrease.
According to an aspect of the present invention, there is provided a decoding method for decoding an encoded bit stream using a look-up table comprising: (a) obtaining index information from a first bit of a codeword formed with bits of a part of the received encoded bit stream, and accessing an entry of the look-up table corresponding to the obtained index information; and (b) determining a type of the entry based on an internal value of the accessed entry.
It is preferable that in step (b) it is determined whether the entry corresponds to an internal node or a terminal node, according to the sign of the internal value of the accessed entry.
It is preferable that the decoding method further comprises: (c) when it is determined in step (b) that the accessed entry corresponds to an internal node, calculating an index value of an entry which will be accessed next, based on an index value of the current entry, the internal value of the accessed entry, and the second bit value of the codeword.
According to another aspect of the present invention, there is provided a decoding apparatus for decoding an encoded bit stream according to a binary tree search, comprising: a processor which decodes the encoded bit stream; and a memory which is connected to the processor and stores a look-up table related to the decoding, wherein the look-up table has entries which correspond to respective nodes of the binary tree and have internal values, and the type of a node of the binary tree corresponding to each entry is determined by the internal value stored in relation with the entry.
It is preferable that the internal value stored in relation with the entry has a different sign according to the type of a node corresponding to the entry.
It is preferable that if the node corresponding to the entry is an internal node, the internal value of the entry is a relative distance value between the internal node which is the current node, and a node to be accessed next.